#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 150;
struct Edge
{
    int v, nxt;
} edge[MAXN];

int head[MAXN * MAXN], cnt;
int linker[MAXN];
bool used[MAXN];
int N, M;

void init()
{
    memset(head, -1, sizeof(head));
    memset(linker, -1, sizeof(linker));
    cnt = 0;
}

void add(int from, int to)
{
    edge[cnt].v = to;
    edge[cnt].nxt = head[from];
    head[from] = cnt++;
}

bool Find(int x)
{
    int v;
    for (int i = head[x]; i != -1; i = edge[i].nxt)
    {
        v = edge[i].v;
        if (used[v])
            continue;
        used[v] = true;
        if (linker[v] == -1 || Find(linker[v]))
        {
            linker[v] = x;
            return true;
        }
    }
    return false;
}

int main()
{
    int T_case, u, v, ans;
    scanf("%d", &T_case);
    while (T_case--)
    {
        init();
        scanf("%d %d", &N, &M);
        while (M--)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
        }
        ans = 0;
        for (int i = 1; i <= N; i++)
        {
            memset(used, 0, sizeof(used));
            if (Find(i))
                ans++;
        }
        printf("%d\n", N - ans);
    }
    return 0;
}